package top.carrotguo.bean.linklist;

/**
 * 双向链表
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 19:28 2018-05-29
 */
public class LinkList<T> {

    public int size;        //链表长度（不包括头尾结点）
    public LinkNode head;   //头结点
    public LinkNode tail;   //尾结点

    /**
     * 初始化双向链表
     */
    public LinkList(){
        init();
    }

    /**
     * 双向链表初始化
     */
    private void init(){
        head = new LinkNode<T>();
        tail = new LinkNode<T>();
        head.nextNode = tail;
        tail.preNode = head;
        head.preNode = null;
        tail.nextNode = null;
        size = 0;
    }

    /**
     * 根据位置查找
     * @return
     */
    public T findByR(int r){
        LinkNode<T> p = head;
        //判断链表是否有元素
        if (size<0 || size<=r) {
            return null;
        }
        p = p.nextNode;
        while (0<r--) {
            p = p.nextNode;
        }
        return p.value;
    }

    /**
     * 在P的n个前驱的查找算法(如有重复  返回最后面那个)
     * @param e  查找元素
     * @param n  n个前驱
     * @param p  当前指向的位置
     * @return
     */
    public LinkNode<T> find(T e, int n, LinkNode<T> p){
        while (0<n--) {
            if (p.preNode != head) {
                if (e == (p=p.preNode).value) {
                    return p;
                }
            }
        }
        return null;
    }

    /**
     * 在P个n的后继的查找算法（如有重复 返回最前面那个）
     * @param e 查找元素
     * @param p 当前指向结点
     * @param n n个后继
     * @return
     */
    public LinkNode<T> find(T e, LinkNode<T> p, int n){
        while (0<n--) {
            if (p.nextNode != tail) {
                if (e == (p=p.nextNode).value) {
                    return p;
                }
            }
        }
        return null;
    }

    /**
     * 前驱插入算法
     * @param p 插入位置
     * @param e 插入元素
     * @return  插入的结点
     */
    public LinkNode<T> insertBefore(T e,LinkNode<T> p){
        size++;
        return p.insertAsPred(e);
    }

    /**
     * 后继插入
     * @param p 插入位置
     * @param e 插入元素
     * @return  插入的结点
     */
    public LinkNode<T> insertAfter(LinkNode<T> p, T e){
        size++;
        return p.insertAsSucc(e);
    }

    /**
     * 在链表尾部插入
     * @param e 插入元素
     * @return
     */
    public LinkNode<T> insertLast(T e){
        LinkNode<T> node = new LinkNode<>();
        node.value = e;
        node.nextNode = tail;
        node.preNode = tail.preNode;
        tail.preNode.nextNode = node;
        tail.preNode = node;
        size++;
        return node;
    }

    /**
     * 删除结点
     * @param p 即将删除的结点
     * @return  删除结点的元素值
     */
    public T remove(LinkNode<T> p){
        T e = p.value;
        p.preNode.nextNode = p.nextNode;
        p.nextNode.preNode = p.preNode;
        size--;
        return e;
    }

    /**
     * 删除链表
     */
    public void clear(){
        while (0<size) {
            //丛头开始删除结点
            remove(head.nextNode);
        }
    }

    /**
     * 无序链表唯一化
     * @return  删除重复元素个数
     */
    public int deduplicate(){
        int oldSize = size;
        int r=1;
        if (size<2) {
            return 0;
        }
        //当前定位在第一个结点
        LinkNode<T> p = head.nextNode;
        //第一次循环定位到第二个结点
        while (tail != (p=p.nextNode)) {
            LinkNode<T> q = find(p.value,r,p);
            if (q!=null) {
                remove(q);
            } else {
                r++;
            }
        }
        return oldSize - size;
    }

    /**
     * 打印链表
     */
    public void printList(){
        LinkNode p = head;
        while ((p = p.nextNode)!=tail) {
            System.out.print(p.value+"  ");
        }
    }

}
